#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include<assert.h>
void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
void SelectSort(int* a, int n)
{
	// 初始化begin为数组的第一个元素
	int begin = 0;

	// 当begin小于n-1时循环，即只要不是数组的最后一个元素，就继续排序
	while (begin < n - 1)
	{
		// 假设当前begin位置的元素是最小的
		int mini = begin;

		// 从begin+1到数组最后一个元素之间查找真正的最小元素
		for (int i = begin + 1; i <= n - 1; i++)
		{
			// 如果找到一个比当前假设的最小元素还要小的元素，更新mini的值
			if (a[i] < a[mini])
			{
				mini = i;
			}
		}

		// 将找到的最小元素与begin位置的元素交换
		Swap(&a[mini], &a[begin]);

		// 交换完成后，begin位置的元素已经是正确的元素，将begin向后移动一位
		begin++;
	}
}
void SelectSort2(int* a, int n)
{
	// 初始化begin为数组的起始位置，end为数组的末尾位置
	int begin = 0;
	int end = n - 1;

	// 当begin小于end时，表示数组中还有元素未排序
	while (begin < end)
	{
		// 初始化最小元素和最大元素的索引为begin
		int mini = begin;
		int maxi = begin;

		// 从begin+1到end遍历数组，寻找当前未排序部分的最小和最大元素
		for (int i = begin + 1; i <= end; i++)
		{
			// 如果当前元素大于已知最大元素的值，更新最大元素的索引
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
			// 如果当前元素小于已知最小元素的值，更新最小元素的索引
			if (a[i] < a[mini])
			{
				mini = i;
			}
		}

		// 将找到的最小元素交换到begin位置
		Swap(&a[mini], &a[begin]);

		// 如果最大元素的索引刚好是begin（此时begin位置的元素已经被最小元素替换了）
		// 那么需要更新最大元素的索引为mini（因为最小元素已经被交换到begin位置）
		if (maxi == begin)
		{
			maxi = mini;
		}

		// 将找到的最大元素交换到end位置
		Swap(&a[maxi], &a[end]);

		// 缩小未排序部分的范围，end向左移动一位，begin向右移动一位
		end--;
		begin++;
	}
}
void TestOP()
{
	//生成N个随机数
	srand(time(0));
	int N = 100000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	assert(a1);
	assert(a2);

	for (int i = 0; i < N - 1; i++)
	{
		a1[i] = rand();
		a2[i] = a1[i];

	}

	//clock函数计算排序函数运行的时间
	int begin1 = clock();
	SelectSort(a1, N);
	int end1 = clock();

	//clock函数计算排序函数运行的时间
	int begin2 = clock();
	SelectSort2(a2, N);
	int end2 = clock();

	printf("SelectSort:%d\n", end1 - begin1);

	printf("SelectSort2:%d\n", end2 - begin2);

	//释放空间
	free(a1);
	//释放空间
	free(a2);


}
int main()
{
	//单向选择排序
	TestOP();
	return 0;
}